﻿#pragma once
#include<iostream>
#include<vector>
using std::string;
namespace open_address
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};
	template<class K, class V>
	struct HashData
	{
		State _state = EMPTY;
		std::pair<K, V> _kv;
	};
	template<class K>
	struct HashFunc
	{
		const K& operator()(const K& key)
		{
			return size_t(key);
		}
	};
	//string 版本用一个特化——除留余数法
	template<>
	struct HashFunc<std::string>
	{
		size_t operator()(const std::string& str)
		{
			int hash = 0;
			for (auto e : str)
			{
				hash *= 131; hash += e;
			}
			return hash;
		}
	};
	template<class K, class V, class hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		bool Insert(const std::pair<K, V>& kv)
		{
			if (Find(kv.first))return false;

			hash hs;
			int hashi = hs(kv.first) % _tables.size();
			//线性探测
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == DELETE)
					break;
				hashi++;
				hashi %= _tables.size();
			}
			//插入数据
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			_n++;
			//判断是否需要扩容
			if (_n / _tables.size() * 10 > 7)
			{
				//std::vector<HashData<K, V>> tmp(_tables.size()*2);
				//for (auto e : _tables)
				//{
				//	if (e._state == EXIST)
				//	{
				//		int index = hs(e._kv.first) % tmp.size();
				//		tmp[index]._state = EXIST;
				//		tmp[index]._kv = e._kv;
				//	}				
				//}
				//_tables.swap(tmp);

				//复用代码
				HashTable<K, V> newTH;
				newTH._tables.resize(_tables.size() * 2);
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
						newTH.Insert(e._kv);
				}
				_tables.swap(newTH._tables);
			}
			return true;
		}
		HashData<K, V>* Find(const K& key)
		{
			hash hs;
			int hashi = hs(key) % _tables.size();
			//线性探测
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			hash hs;
			//int hashi = hs(key) % _tables.size();
			////线性探测
			//while (_tables[hashi]._state != EMPTY)
			//{
			//	if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
			//	{
			//		_tables[hashi]._states = DELETE;
			//		_n--;
			//		return true;
			//	}
			//	hashi++;
			//	hashi %= _tables.size();
			//}
			//return false;

			//简便写法——代码复用
			if (Find(key) != nullptr)
			{
				int hashi = hs(key) % _tables.size();
				_tables[hashi]._state = DELETE;
				return true;
			}
			else
			{
				return false;
			}
		}
	private:
		std::vector<HashData<K, V>> _tables;
		size_t _n = 0;
	};
}

